package golang

import (
	"gitee.com/allowall-package/goutil/fn"
)

// 插入排序
func InsertionSort(a []int) []int {
	n := len(a)

	if n < 1 {
		return a
	}

	for i := 1; i < n; i++ {
		// 每轮需要插入的值
		v := a[i]
		j := i - 1
		for ; j >= 0; j-- {
			if v < a[j] {
				a[j+1] = a[j]
			} else {
				break
			}
		}

		a[j+1] = v
	}

	return a
}

func InsertionSortTest() {
	fn.SliceRand(a)
	s := make([]int, len(a))
	copy(s, a)

	InsertionSort(a)

	fn.Dump(fn.FuncInfo(), s, a)
}
